#include <iostream>
#include <cstdio>

using namespace std;

class node{
    public:
        node* next;
        node* prev;
        int data;
    node(int val) : next(nullptr) , prev(nullptr)  , data(val) {}
};

class DoubleLL{
    private:
        node* head;
        node* tail;
    public:
        DoubleLL()  : head(nullptr) , tail(nullptr) {}
        
        void headinsert(int val){//头插
            //头节点为空
            node* newnode = new node(val);
            newnode->next = head;
            //头节点非空
            if(head != nullptr){
                head->prev = newnode;
            }
            head = newnode;
            //(插入之前)整张表为空
            if(tail == nullptr){
                tail = head;
            }
        }

        void tailinsert(int val){//尾插
            node* newnode = new node(val);
            if(tail == nullptr){ //尾指针为空 <==> 整张表是空的
                delete newnode;
                headinsert(val); //懒得写了（
                return;
            }
            newnode->prev = tail;
            tail->next = newnode;
            tail = newnode;
        }
        
        void insertleft(int val, int data){ //值为val的左边插入data
            node* newnode = new node(data);
            node* cur = head;
            node* target = nullptr;
            while(cur != nullptr){
                if(cur->data == val){
                    target = cur;
                    break;
                }
                cur = cur->next;
            }
            if(target == nullptr)    return;
            else if(target->prev == head){
                delete newnode;
                headinsert(data);
            }
            else{
                newnode->next = target;
                target->prev->next = newnode;
                newnode->prev = target->prev;
                target->prev = newnode;
            }
        }

        void insertright(int val, int data){ //值为val的右边插入data
            node* newnode = new node(data);
            node* cur = head;
            node* target = nullptr;
            while(cur->next != nullptr){
                if(cur->data == val){
                    target = cur;
                    break;
                }
                cur = cur->next;
            }
            if(target == nullptr)    return;
            else if(target->next == tail){
                delete newnode;
                tailinsert(data);
            }
            else{
                newnode->next = target->next;
                target->next->prev = newnode;
                target->next = newnode;
                newnode->prev = target;
            }
        }

        void del(int val){ //删除值为x的，出现在最前面的
            node* cur = head;
            node* target = nullptr;
            while(cur->next != nullptr){
                if(cur->data == val){
                    target = cur;
                    break;
                }
                cur = cur->next;
            }
            if(target == nullptr)   return;
            if(target == head){
                head = head->next;
                delete target;
            }else if(target == tail){
                tail = tail->prev;
                delete target;
            }else{
                target->prev->next = target->next;
                target->next->prev = target->prev;
                delete target;
            }
        }

        void printforward(){
            node* cur = head;
            while(cur != nullptr){
                cout << cur->data << " ";
                cur = cur->next;
            }
        }

        void printbackward(){
            node* cur = tail;
            while(cur != nullptr){
                cout << cur->data << " ";
                cur = cur->prev;
            }
        }
};

int main(){
    DoubleLL l;
    l.headinsert(1);
    l.printforward();
    return 0;
}